package am

import "fmt"

const INF = 65535

type VertexType string

type AMGraph struct {
	Vers    []VertexType
	Arcs    [][]int
	NumVers int
	NumArcs int
}

// 根据自定义信息创建图 (邻接矩阵)
func CreateGraph() *AMGraph {
	o := &AMGraph{}
	fmt.Println("请输入顶点和边数")
	fmt.Scanf("%d %d", &o.NumVers, &o.NumArcs)

	//初始化AMGraph
	o.Vers = make([]VertexType, o.NumVers)
	o.Arcs = make([][]int, o.NumVers)
	for i := 0; i < o.NumVers; i++ {
		o.Arcs[i] = make([]int, o.NumVers)
	}

	for i := 0; i < o.NumArcs; i++ {
		for j := 0; j < o.NumVers; j++ {
			o.Arcs[i][j] = INF
		}
	}

	//输入顶点信息
	fmt.Println("请输入顶点信息")
	for i := 0; i < o.NumVers; i++ {
		fmt.Scanf("%s", &o.Vers[i])
	}

	//输入边信息
	fmt.Println("请输入边信息")
	for i := 0; i < o.NumArcs; i++ {
		var m, n, v int
		fmt.Scanf("%d %d %d", &m, &n, &v)
		o.Arcs[m][n] = v
	}

	return o
}

// 打印arcs矩阵信息
func (g *AMGraph) Print() {
	fmt.Printf("%5s ", "")
	for i := 0; i < g.NumVers; i++ {
		fmt.Printf("%5s ", g.Vers[i])
	}
	fmt.Println()
	for i := 0; i < g.NumVers; i++ {
		fmt.Printf("%5s ", g.Vers[i])
		for j := 0; j < g.NumVers; j++ {
			if j == g.NumVers-1 {
				formatPrint(g.Arcs[i][j])
				fmt.Println()
			} else {
				formatPrint(g.Arcs[i][j])
			}
		}
	}
}

// 深度优先遍历
func (g *AMGraph) DFS(i int) {
	visited := make([]bool, g.NumVers)
	var dfsHelper func(i int)
	dfsHelper = func(i int) {
		{
			fmt.Printf("%s ", g.Vers[i])
			visited[i] = true
			for j := 0; j < g.NumVers; j++ {
				if !visited[j] && g.Arcs[i][j] < INF {
					dfsHelper(j)
				}
			}
		}
	}

	dfsHelper(i)
}

// 广度优先遍历
func (g *AMGraph) BFS(x int) {
	q := make([]int, 0)
	visited := make([]bool, g.NumVers)
	q = append(q, x)
	visited[x] = true
	fmt.Printf("%s ", g.Vers[x])
	for len(q) != 0 {
		i := q[0]
		q = q[1:]
		for j := 0; j < g.NumVers; j++ {
			if !visited[j] && g.Arcs[i][j] < INF {
				fmt.Printf("%s ", g.Vers[j])
				q = append(q, j)
				visited[j] = true
			}
		}
	}
}

func (g *AMGraph) Mst_prim(x int) {
	visited := make([]bool, g.NumVers)
	cost := make([]int, g.NumVers)
	adjvex := make([]int, g.NumVers)
	visited[x] = true
	for i := 0; i < g.NumVers; i++ {
		adjvex[i] = x
		cost[i] = g.Arcs[x][i]
	}

	for w := 1; w < g.NumVers; w++ {
		min := INF
		k := 0
		for i := 0; i < g.NumVers; i++ {
			if !visited[i] && cost[i] < min {
				min = cost[i]
				k = i
			}
		}

		fmt.Printf("v%d v%d %d\n", adjvex[k], k, min)
		visited[k] = true

		for i := 0; i < g.NumVers; i++ {
			if !visited[i] && g.Arcs[k][i] < cost[i] {
				adjvex[i] = k
				cost[i] = g.Arcs[k][i]
			}
		}
	}
}

func (g *AMGraph) Mst_kruskal() {

}

// 求v0至vx的最短路径
func (g *AMGraph) Shortestpath_Dj(v0 int, vx int) {
	//初始化
	visited := make([]bool, g.NumVers)
	D := make([]int, g.NumVers)
	P := make([]int, g.NumVers)
	for i := 0; i < g.NumVers; i++ {
		D[i] = g.Arcs[v0][i]
		P[i] = -1
	}
	visited[v0] = true

	for w := 1; w < g.NumVers; w++ {
		min := INF
		k := 0
		for i := 0; i < g.NumVers; i++ {
			if !visited[i] && D[i] < min {
				min = D[i]
				k = i
			}
		}

		visited[k] = true
		for i := 0; i < g.NumVers; i++ {
			if !visited[i] && g.Arcs[k][i]+min < D[i] {
				D[i] = g.Arcs[k][i] + min
				P[i] = k
			}
		}
	}

	s := make([]int, 0)
	t := vx
	for t != -1 {
		s = append(s, t)
		t = P[t]
	}

	fmt.Printf("v%d->", v0)
	for len(s) != 0 {
		i := s[len(s)-1]
		s = s[:len(s)-1]
		fmt.Printf("v%d", i)
		if len(s) != 0 {
			fmt.Print("->")
		}
	}
	//scan
	//add
	//update
}

func (g *AMGraph) Shortestpath_floyd() {
	D := createMetrix(g.NumVers)
	P := createMetrix(g.NumVers)
	for i := 0; i < g.NumVers; i++ {
		for j := 0; j < g.NumVers; j++ {
			D[i][j] = g.Arcs[i][j]
			P[i][j] = j
		}
	}
	for k := 0; k < g.NumVers; k++ {
		for i := 0; i < g.NumVers; i++ {
			for j := 0; j < g.NumVers; j++ {
				if D[i][k]+D[k][j] < D[i][j] {
					D[i][j] = D[i][k] + D[k][j]
					P[i][j] = P[i][k]
				}
			}
		}
	}
	fmt.Println()
	for i := 0; i < g.NumVers; i++ {
		for j := i + 1; j < g.NumVers; j++ {
			k := P[i][j]
			fmt.Printf("v%d", i)
			for k != j { // 这块需要再想想
				fmt.Printf("->v%d", k)
				k = P[k][j]
			}
			fmt.Printf("->v%d", j)
			fmt.Println()
		}
	}
}

// 对于无限大值打印时替换为inf
func formatPrint(x int) {
	if x == INF {
		fmt.Printf("%5s ", "inf")
	} else {
		fmt.Printf("%5d ", x)
	}
}

/*
*
构建有向非连通图

		图例![](http://cdn.bsummer.cn/20200316001005.png)
	        v0    v1    v2    v3    v4
	  v0     0   inf   inf   inf     6
	  v1     9     0     3   inf   inf
	  v2     2   inf     0     5   inf
	  v3   inf   inf   inf     0     1
	  v4   inf   inf   inf   inf     0
*/
func CreateDirectedNoConnectedGraph() *AMGraph {
	o := &AMGraph{}
	o.NumVers = 5
	o.NumArcs = 6
	o.Vers = []VertexType{"v0", "v1", "v2", "v3", "v4", "v5"}
	o.Arcs = [][]int{}
	o.Arcs = append(o.Arcs, []int{0, INF, INF, INF, 6})
	o.Arcs = append(o.Arcs, []int{9, 0, 3, INF, INF})
	o.Arcs = append(o.Arcs, []int{2, INF, 0, 5, INF})
	o.Arcs = append(o.Arcs, []int{INF, INF, INF, 0, 1})
	o.Arcs = append(o.Arcs, []int{INF, INF, INF, INF, 0})
	return o
}

/*
*
构建无向连通图

			图例![](http://cdn.bsummer.cn/20200316023155.png)
	         v0    v1    v2    v3    v4    v5    v6    v7    v8
	   v0     0    10   inf   inf   inf    11   inf   inf   inf
	   v1    10     0    18   inf   inf   inf    16   inf    12
	   v2   inf   inf     0    22   inf   inf   inf   inf     8
	   v3   inf   inf    22     0    20   inf   inf    16    21
	   v4   inf   inf   inf    20     0    26   inf     7   inf
	   v5    11   inf   inf   inf    26     0    17   inf   inf
	   v6   inf    16   inf   inf   inf    17     0    19   inf
	   v7   inf   inf   inf    16     7   inf    19     0   inf
	   v8   inf    12     8    21   inf   inf   inf   inf     0
*/
func CreateNoDirectedConnectedGraph() *AMGraph {
	o := &AMGraph{}
	o.NumVers = 9
	o.NumArcs = 15
	o.Vers = []VertexType{"v0", "v1", "v2", "v3", "v4", "v5", "v6", "v7", "v8"}
	o.Arcs = [][]int{}
	o.Arcs = append(o.Arcs, []int{0, 10, INF, INF, INF, 11, INF, INF, INF})
	o.Arcs = append(o.Arcs, []int{10, 0, 18, INF, INF, INF, 16, INF, 12})
	o.Arcs = append(o.Arcs, []int{INF, INF, 0, 22, INF, INF, INF, INF, 8})
	o.Arcs = append(o.Arcs, []int{INF, INF, 22, 0, 20, INF, INF, 16, 21})
	o.Arcs = append(o.Arcs, []int{INF, INF, INF, 20, 0, 26, INF, 7, INF})
	o.Arcs = append(o.Arcs, []int{11, INF, INF, INF, 26, 0, 17, INF, INF})
	o.Arcs = append(o.Arcs, []int{INF, 16, INF, INF, INF, 17, 0, 19, INF})
	o.Arcs = append(o.Arcs, []int{INF, INF, INF, 16, 7, INF, 19, 0, INF})
	o.Arcs = append(o.Arcs, []int{INF, 12, 8, 21, INF, INF, INF, INF, 0})
	return o
}

func createMetrix(n int) [][]int {
	o := [][]int{}
	for i := 0; i < n; i++ {
		o = append(o, make([]int, n))
	}
	return o
}
